package com.hejjon.demo01;

import com.hejjon.util.TimeTool;

/**
 *  斐波那契数列
 * Created by caoshi at 22:55 2021-09-29
 *  0 1 1 2 3 5
 */
public class FibonacciDemo {


    /**
     * 递归方式计算
     * @param n
     * @return
     */
    public static int fib(int n) {
        if (n == 0 || n == 1) return n;

        return fib(n - 2) + fib(n - 1);
    }
    public static int fib2(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;

        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }

        return second;
    }



    public static void main(String[] args) {
//        System.out.println(fib(0));
//        System.out.println(fib(3));
//        System.out.println(fib(1));
//        System.out.println(fib(4));
       // System.out.println(fib2(64));
        TimeTool.check("fib2", () -> {
            System.out.println(fib2(13));
        });


    }



}
